# Hungary：利用广度优先搜索每个点的增广路

from tools.Conversion import Conversion
from tools.Input import Input
from tools.Output import Output


class Hungarian:
    __name = 'Hungarian'

    @staticmethod
    def do_hungary():
        # g = Input.input_bipartite_graph()  # 输入二部图
        g = Conversion.bipartite_graph_arr_2_matrix(Input.get_bipartite_graph())  # 获取一个图（例5.4.2）
        print('输入的图为：')
        Output.print_bipartite_graph_matrix(g)

        v_set1 = g[0][0]  # v1中的点集
        match_set = {}  # 匹配（key:v_set2，value:v_set1）
        searched_path = []  # 增广路

        print('生成过程：')
        for v1_index in range(len(v_set1)):
            v1 = v_set1[v1_index]
            if v1 not in match_set.values():  # 找到不在匹配中的点
                searched_path.clear()
                find = Hungarian.find_match(g, v1_index, searched_path, match_set)  # 找匹配
                if find and len(searched_path) > 2:
                    print('找到增广路', searched_path)

        print('最大匹配：')
        Output.print_match(match_set)

    ''' 从v1中找匹配（深度优先遍历） '''

    @staticmethod
    def find_match(g, v1_index, searched_path, v_set_match):
        v_set1 = g[0][0]
        v_set2 = g[0][1]  # 点集
        s_set = g[1]  # 边集（邻接矩阵）

        v1 = v_set1[v1_index]
        searched_path.append(v1)  # 加入v_set1中的点v1

        for v2_index in range(len(v_set2)):
            v2 = v_set2[v2_index]
            if s_set[v1_index][v2_index] != 0 and v2 not in searched_path:  # index不在已搜索路中的邻边
                searched_path.append(v2)  # 加入v_set1中的点v1
                if v2 not in v_set_match.keys() or Hungarian.find_match(g, v_set1.index(v_set_match[v2]), searched_path,
                                                                        v_set_match):  # v2不在匹配中或v2匹配的点有增广路
                    v_set_match.update({v2: v1})  # 将v2:v1加入匹配
                    return True
        return False
